import math
import random

def Kmeans(data, k, epsilon=1e-4, max_iterations=100):
    # 辅助函数：计算两个向量的欧氏距离
    def euclidean_distance(a, b):
        return math.sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))

    # 辅助函数：将样本分配到最近的聚类中心
    def assign_cluster(x, c):
        min_distance = float('inf')
        cluster_index = 0
        for i, centroid in enumerate(c):
            distance = euclidean_distance(x, centroid)
            if distance < min_distance:
                min_distance = distance
                cluster_index = i
        return cluster_index

    # 初始化聚类中心 - 随机选择k个样本
    c = random.sample(data, k)

    # 初始化labels变量
    labels = []

    # 迭代优化
    for _ in range(max_iterations):
        # 分配样本到最近的聚类中心
        clusters = [[] for _ in range(k)]
        labels = []  # 重新初始化labels

        for sample in data:
            cluster_idx = assign_cluster(sample, c)
            clusters[cluster_idx].append(sample)
            labels.append(cluster_idx)

        # 重新计算聚类中心
        new_c = []
        total_movement = 0.0

        for i in range(k):
            if clusters[i]:  # 如果簇不为空
                # 计算簇内均值作为新中心
                dimension = len(clusters[i][0])
                new_center = [0.0] * dimension

                for point in clusters[i]:
                    for d in range(dimension):
                        new_center[d] += point[d]

                for d in range(dimension):
                    new_center[d] /= len(clusters[i])

                new_c.append(new_center)

                # 计算中心移动距离
                movement = euclidean_distance(c[i], new_center)
                total_movement += movement
            else:
                # 如果簇为空，随机重新初始化该中心
                new_c.append(random.choice(data))

        # 检查收敛条件
        if total_movement < epsilon:
            break

        c = new_c

    return c, labels